package wtx.geeks;

import java.util.Arrays;

/**
 * https://practice.geeksforgeeks.org/problems/max-length-chain/1
 */
public final class MaxChainLen {
  public static class Pair {
    int x;
    int y;
    
    public Pair(int a, int b) {
        x = a;
        y = b;
    }
  }

  int maxChainLength(Pair arr[], int n) {
    Arrays.sort(arr, (p1, p2) -> Integer.compare(p1.y, p2.y));
    int l = 1;
    int prev = 0;
    for (int i = 1; i < arr.length; ++i) {
      if (arr[prev].y < arr[i].x) {
        prev = i;
        ++l;
      }
    }
    return l;
  }

  /**
   * Says hello to the world.
   * 
   * @param args
   *               The arguments of the program.
   */
  public static void main(String[] args) {
    MaxChainLen solution = new MaxChainLen();
    Pair[] arr = new Pair[5];
    arr[0] = new Pair(5, 24);
    arr[1] = new Pair(39, 60);
    arr[2] = new Pair(15, 28);
    arr[3] = new Pair(27, 40);
    arr[4] = new Pair(50, 90);
    System.out.println(solution.maxChainLength(arr, arr.length));
  }
}
